﻿//T1 ⻓度最⼩的⼦数组 力扣
//思路：滑动窗口，循环判断出窗口
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int left = 0, right = 0;
//        int ret = INT_MAX;
//        int sum = 0;
//        for (; right < nums.size(); right++)
//        {
//            sum += nums[right];
//            while (sum >= target)
//            {
//                ret = min(ret, right - left + 1);
//                sum -= nums[left++];
//            }
//        }
//        if (ret == INT_MAX)
//            ret = 0;
//        return ret;
//    }
//};

//T2 无重复字符的最长子串 力扣
//思路：滑动窗口，hash数组统计字符数（128）
//class Solution {
//public:
//    int lengthOfLongestSubstring(string s) {
//        int hash[128] = { 0 };
//        int left = 0, right = 0;
//        int ret = 0;
//        for (; right < s.size(); right++) {
//            hash[s[right]]++;
//            while (hash[s[right]] > 1)
//                hash[s[left++]]--;
//            ret = max(ret, right - left + 1);
//        }
//        return ret;
//    }
//};

//T3 最⼤连续1的个数III 力扣
//思路：进窗口，right==0时，计数++，大于k时，left出窗口直到，0计数小于k
//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        int ret = 0, zero = 0;
//        int left = 0, right = 0;
//        int n = nums.size();
//        while (right < n) {
//            if (nums[right++] == 0) {
//                zero++;
//                while (zero > k)
//                    if (nums[left++] == 0)
//                        zero--;
//            }
//            ret = max(ret, right - left);
//        }
//        return ret;
//    }
//};

//T4 将x减到0的最小操作数 力扣
//思路：正难则反，利用滑动窗口求出子数组和等于 数组所有元素和 减去 x 的最长子数组
//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x) {
//        int sum = 0, n = nums.size();
//        for (auto e : nums)
//            sum += e;
//        int target = sum - x;
//        int ret = -1;
//        sum = 0;
//        if (target < 0)
//            return -1;
//        for (int left = 0, right = 0; right < n; right++) {
//            sum += nums[right];
//            while (sum > target)
//                sum -= nums[left++];
//            if (sum == target)
//                ret = max(ret, right - left + 1);
//        }
//        if (ret == -1)
//            return ret;
//        else
//            return n - ret;
//    }
//};


//T5 水果成篮 力扣
//思路：（题干中的fruits[i]为水果类型的编号）
//class Solution {
//public:
//    int hash[100000] = { 0 };
//    int totalFruit(vector<int>& fruits) {
//        int n = fruits.size();
//        int left = 0, right = 0;
//        int types = 0;
//        int ret = 0;
//        for (; right < n; right++) {
//            if (hash[fruits[right]]++ == 0)
//                types++;
//            while (types > 2)
//                if (hash[fruits[left++]]-- == 1)
//                    types--;
//            ret = max(ret, right - left + 1);
//        }
//        return ret;
//    }
//};

//T6 找到字符串中所有字母易位词 力扣
//思路：定长的滑动数组
//	   检测是否为易位词的方法，定义两个hash数组，逐个元素比较（本题满足条件，可以优化）
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p) {
//        int hashp[26] = { 0 };
//        int hashs[26] = { 0 };
//        int n = p.size();
//        for (auto e : p)
//            hashp[e - 'a']++;
//        vector<int> ret;
//        for (int left = 0, right = 0; right < s.size(); right++) {
//            hashs[s[right] - 'a']++;
//            if (right - left + 1 > n)
//                hashs[s[left++] - 'a']--;
//            int i = 0;
//            for (; i < 26; i++)
//                if (hashp[i] != hashs[i])
//                    break;
//            if (i == 26)
//                ret.push_back(left);
//        }
//        return ret;
//    }
//};

//T6 找到字符串中所有字母易位词 力扣(检测优化）
//思路：不同于上方的依次比较数组的26个字符，该方法：使用count计数，当hashs中对应位置的计数+1后，
//		小于等于hashp中的时，说明记录的都是有效字符，大于时，说明是额外的字符，count只记录有效字符，
//		因此count不变。
//		当出窗口时，如果当hashs中对应位置小于等于hashp中的时，说明要出的为有效字符，count--。
//		通过right-left+1来判断当前滑动数组的大小与字符串p的字符数是否相同。
//		当有效字符个数count与字符串p的字符个数相等时，说明两个hash数组一致，满足条件。
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p) {
//        int hashp[26] = { 0 };
//        int hashs[26] = { 0 };
//        int n = p.size();
//        for (auto e : p)
//            hashp[e - 'a']++;
//        vector<int> ret;
//        int count = 0;
//        for (int left = 0, right = 0; right < s.size(); right++) {
//            if (++hashs[s[right] - 'a'] <= hashp[s[right] - 'a'])
//                count++;
//            if (right - left + 1 > n) {
//                char tmp = s[left++];
//                if (hashs[tmp - 'a']-- <= hashp[tmp - 'a'])
//                    count--;
//            }
//            if (count == n)
//                ret.push_back(left);
//        }
//        return ret;
//    }
//};


//T7 串联所有单词的子串 力扣
//思路：将每一个子串看作一个字符时，该题目与T6思路一致
//class Solution {
//public:
//    vector<int> findSubstring(string s, vector<string>& words) {
//        unordered_map<string, int> hashw;
//        vector<int> ret;
//        for (auto& e : words)
//            hashw[e]++;
//        int len = words[0].size();
//        for (int i = 0; i < len; i++) {
//            unordered_map<string, int> hashs;
//            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len) {
//                // 进窗口
//                string in = s.substr(right, len);
//                hashs[in]++;
//                if (hashs[in] <= hashw[in])
//                    count++;
//                // 出窗口
//                if (right - left + 1 > len * words.size()) {
//                    string out = s.substr(left, len);
//                    if (hashs[out] <= hashw[out])
//                        count--;
//                    hashs[out]--;
//                    left += len;
//                }
//                if (count == words.size())
//                    ret.push_back(left);
//            }
//        }
//        return ret;
//    }
//};


//T8 最小覆盖子串 力扣
//思路： 创建两个数组哈希表，表s中对应的字符个数==表t中的时，count++，说明该字符是有效的
//		出窗口时，同样相等时，count--。
//		1.进窗口，hash[right++]++;
//		2.判断，当count与表t中的有效字符个数相等时，出窗口
//		3.更新结果
//		4.出窗口 hash[left++]--
//class Solution {
//public:
//    string minWindow(string s, string t) {
//        char hashs[128] = { 0 };
//        char hasht[128] = { 0 };
//        string ret;
//        int kind = 0;
//        for (auto e : t) {
//            if (hasht[e]++ == 0)
//                kind++;
//        }
//        int minlen = INT_MAX, begin = -1;
//        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
//            int tmp = s[right];
//            if (++hashs[tmp] == hasht[tmp])
//                count++;
//            while (count == kind) {
//                if (right - left + 1 <= minlen) {
//                    minlen = right - left + 1;
//                    begin = left;
//                }
//                int out = s[left++];
//                if (hashs[out]-- == hasht[out])
//                    count--;
//            }
//        }
//        if (begin == -1)
//            return "";
//        else
//            return s.substr(begin, minlen);
//    }
//};